#include <stdio.h>
#include <cstdlib>

struct TreeNode;
typedef struct TreeNode *Position;
typedef struct TreeNode *SearchTree;

SearchTree MakeEmpty( SearchTree T );
Position Find( int X, SearchTree T);
Position FindMin( SearchTree T );
Position FindMax( SearchTree T );
SearchTree Insert( int X, SearchTree T );
SearchTree Delete( int X, SearchTree T );
int Retrieve( Position P );

struct TreeNode
{
    int Element;
    SearchTree Left;
    SearchTree Right;
};

SearchTree
MakeEmpty( SearchTree T)
{
    if( T != NULL)
    {
        MakeEmpty( T -> Left);
        MakeEmpty( T -> Right);
        free( T );//free操作不会删除T节点？
    }
    return NULL;
}

Position
Find( int X , SearchTree T)
{
    if ( T == NULL )
        return  NULL;
    if ( X  < T -> Element)
        return Find( X, T ->Left );
    else if( X > T -> Element)
            return Find( X, T ->Right);
    else return T;
}

Position
FindMin( SearchTree T )
{
    if( T == NULL )
        return NULL;
    else if( T -> Left == NULL)
        return T;
    else return ( T -> Left );
}

Position
FindMax( SearchTree T )
{
    if( T != NULL)
        while( T -> Right != NULL)
            T = T -> Right;

    return T;
}

SearchTree
Insert( int X , SearchTree T)
{
    if( T == NULL )
    {
        T = malloc( sizeof( struct TreeNode));
        if( T == NULL)
            printf( "Out of space !!!");
        else
        {
            T ->Element = X;
            T ->Left = T ->Right = NULL;
        }
    }
    else if( X < T ->Element)
        T ->Left = Insert( X, T ->Left);
    else if( X > T ->Element)
        T ->Right = Insert( X, T ->Right);
    else
        printf("This element is already in the Tree");
    return T;
}

SearchTree
Delete( int X , SearchTree T)
{
    Position TmpCell;

    if( T == NULL )
        printf("Element not found ");
    else if( X < T ->Element)
        T ->Left = Delete(X , T ->Left);
    else if( X > T ->Element)
        T ->Right = Delete( X , T -> Right);
    else if( T ->Right && T->Left)
    {
        TmpCell = FindMin( T -> Right);
        T ->Element = TmpCell->Element;
        T ->Right = Delete( T ->Element, T ->Right);
    }
    else
    {
        TmpCell = T;
        if( T->Left == NULL)
            T = T->Right;
        else if ( T -> Right == NULL)
            T = T ->Left;
        free( TmpCell );
    }
    return T;
}